package leetcode.to1000;

import org.junit.Test;

import java.util.Arrays;

public class T0743 {

    public  int networkDelayTime(int[][] times, int n, int k) {
        k--;
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE / 2);
            matrix[i][i] = 0;
        }
        for (int[] time : times) {
            matrix[time[0] - 1][time[1] - 1] = time[2];
        }
        //判断该点的最短路径是否求出
        boolean[] visited = new boolean[n];

        //初始化源节点
        visited[k] = true;

        for (int i = 1; i < n; i++) {
            int min = Integer.MAX_VALUE / 2;
            int index = -1;

            for (int j = 0; j < n; j++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                if (!visited[j] && (index == -1 ||matrix[k][j] < min)) {
                    min = matrix[k][j];
                    index = j;
                }
            }

            //更新最短路径
            visited[index] = true;

            //更新从index跳到其它节点的较短路径
            for (int m = 0; m < n; m++) {
                if (!visited[m] && matrix[k][index] + matrix[index][m] < matrix[k][m]) {
                    matrix[k][m] = matrix[k][index] + matrix[index][m];
                }
            }
        }
        int max = -1;
        for (int i = 0; i < n; i++) {
            if (matrix[k][i] == Integer.MAX_VALUE / 2) {
                return -1;
            } else {
                if (matrix[k][i] > max) {
                    max = matrix[k][i];
                }
            }
        }
        return max;
    }
    @Test
    public  void test() {
        int[][] num=new int[1][3];
        num[0][0]=1;
        num[0][1]=2;
        num[0][2]=1;
        networkDelayTime(num,2,2);
    }

    class Solution2 {
        public int networkDelayTime(int[][] times, int n, int k) {
            final int INF = Integer.MAX_VALUE / 2;
            int[][] g = new int[n][n];
            for (int i = 0; i < n; ++i) {
                Arrays.fill(g[i], INF);
            }
            for (int[] t : times) {
                int x = t[0] - 1, y = t[1] - 1;
                g[x][y] = t[2];
            }

            int[] dist = new int[n];
            Arrays.fill(dist, INF);
            dist[k - 1] = 0;
            boolean[] used = new boolean[n];
            for (int i = 0; i < n; ++i) {
                int x = -1;
                for (int y = 0; y < n; ++y) {
                    if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                        x = y;
                    }
                }
                used[x] = true;
                for (int y = 0; y < n; ++y) {
                    dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
                }
            }

            int ans = Arrays.stream(dist).max().getAsInt();
            return ans == INF ? -1 : ans;
        }
    }
}
